Multi-hop wireless networks have been the subject of much study over the past decade. Much of the original work was motivated by military applications such as battlefield communications. More recently, however, some interesting commercial applications have emerged which has led to a surge of interest in building wireless neighborhood, or mesh, networks. One example is “community wireless mesh networks”, where a multi-hop wireless network, perhaps based on the IEEE 802.11 standard, is used to provide “last-mile” broadband Internet access to peoples' homes.
There are several advantages to enabling such connectivity. For example, when enough neighbors cooperate and forward each others packets, they do not need to individually install dedicated wired Internet connections, but instead can share faster, more cost-effective gateways to the wired Internet that are distributed in their neighborhood. Packets dynamically find a route, hopping from one neighbor's node to another to reach the Internet through one of the gateways. Another advantage of multi-hop wireless mesh technology is that it enables new applications: for example, neighbors can cooperatively deploy distributed backup technology and hence do not have to worry about losing information due to a catastrophic disk failure. A third advantage is that the technology allows data created locally to be used locally without having to employ an Internet service provider. Neighborhood community mesh networks allow faster and easier dissemination of cached information and information that is relevant to the local community.
Unfortunately, simulation studies using actual suburban neighborhood topologies and off-the-shelf IEEE 802.11 wireless hardware have shown that multi-hop wireless mesh networks, where each router node has a single radio frequency transceiver, do not scale well. Further, the current state-of-art wireless LAN technology does not provide the range necessary for making such community networks possible.
To make community mesh networks viable, improvements are needed for both the range of individual links in the mesh network and for the overall capacity of the mesh network. Attaching multiple transceivers and directional antennas to each mesh router is one approach which has shown promise towards meeting these objectives. It should be noted that in the community networking scenario, router mobility is limited and battery capacity is not an issue because the mesh routers are placed in houses and can be plugged in to an electrical outlet.
The above approach is not however void of challenges. Specifically, for directional antennas to be used properly, the sending node needs to point its antenna in the direction of the destination node. To enable even longer-range communications, both the sending and the receiving nodes may need to have their directional antennas aimed properly in order for two routers to communicate. The questions are: 1) how does a sending node know where the destination node is?; and 2) how does the intended receiver know where the sending node is? There have been several attempts to date aimed at developing a neighbor discovery protocol, though each possesses substantial shortcomings.
The Nasipuri Discovery Protocol is designed for nodes with sectorized antennas, where each node in the network is equipped with M non-overlapping directional antennas each of which has the same beamwidth (360°/M) (see A. Nasipuri, S. Ye, J. You, and R. E. Hiromoto, “A MAC Protocol for Mobile Ad Hoc Networks Using Directional Antennas”, IEEE WCNC 2000, September 2000). Each node is expected to maintain the same orientation of its antennas even as it moves. Because of the use of sectorized antennas, an idle node can listen for incoming transmissions on all its antennas and a transmitting node can send a packet in all directions by transmitting on all its antennas. This protocol uses an omni-directional RTS message when the transmitting node wants to send a message and then intended destination responds with a CTS message, also sent omni-directionally. The destination node records which sector it received the RTS message from by determining which antenna had the strongest signal and the source node uses the same technique on the CTS message to determine which sector the destination node is in. Because the nodes are assumed to be mobile, the information about which sector to use is only remembered for transmitting a single packet.
In the Rotational Sector Receive Protocol each node in the network is equipped with one RF transceiver and one antenna. The antenna can be used to transmit and receive either omni-directionally or directionally (see Somprakash Bandyopadhyay, Dola Sana, Siuli Roy, Tetsuro Ueda, Tetsuro Ueda, and Shinsuke Tanaka, “A Network-Aware MAC and Routing Protocol for Effective Load Balancing in Ad Hoc Wireless Networks with Directional Antenna”, ACM MobiHoc 2003, June 2003). When idle, the node defaults to its omni-directional sensing mode and on sensing a packet it switches to a rotational sector receive mode. In rotational mode, the antenna switches sequentially in 45 degrees increments covering the entire 360 degree space around the node.
To locate a particular neighbor, the initiator node transmits each control packet with a 200 microsecond signal tone that precedes the control packet. On sensing the tone, the destination node switches its antenna to rotational mode and receives the tone directionally in all possible directions. The node examines the signal strength in the different directions and settles on the direction which provides the maximum signal strength. It then sets its beam in that direction for receiving the subsequent data reception. The duration of the tone is long enough to allow the destination node to rotate its beam through 360 degrees and receive the tone in each of its distinct directions. Once the location is determined, the node stores the information in its Active Node List (ANL). Every node periodically broadcasts the ANL omni-directionally, preceded by the tone signal. This helps to maintain the validity of location information in the nodes' location cache. An RTS/CTS (Request to Send/Clear to Send) exchange containing the direction of transmission occurs over the omni-directional antenna to inform the neighbors about the impeding communications and reduce the possibility of packet collisions.
Here, the protocol only provides for the case where the sender is transmitting and the receiver is idling. That is, the receiver is listening in an omni-directional way. Not accounted for is the case where the receiver may be busy in an on-going communication. In such a case the receiver would not be able to hear and respond to its neighbor's discovery message and would therefore not be discovered. In addition, the protocol suffers from a constant overhead. When the receiver hears the initial tone, a full 200 microseconds have to pass before the actual control packet can be heard. Another significant disadvantage of this approach is that it only enables neighbor discovery between nodes that are in omni-directional range of each other. Therefore, it does not enable the longer-range communication that should be possible using directional antennas.
In the Circular RTS Protocol (see T. Korakis, G. Jakllari, and L. Tassiulas “A MAC Protocol for Full Exploitation of Directional Antennas in Ad-hoc Wireless Networks”, ACM Mobihoc 2003, June 2003) each node in the network is equipped with one RF transceiver and one antenna that can receive omni-directionally or directionally, but can only transmit directionally. No other details of the antenna are specified for this protocol. The model is that omni-directional transmissions are achieved with successive sequential directional transmissions. On packet reception, the node is able to use selection diversity, defined as the capability to ascertain the direction from which the packet arrived. Selection diversity is assumed possible by selecting the combination of antenna elements which sense the maximum signal power. Although this antenna model is not a traditional sectorized antenna, it has many similarities.
In this protocol the transmitter begins by consecutively sending an RTS packet, once in each of the possible directions, in a predefined sequence, covering the entire area around the node. Each of the neighboring nodes receives this RTS in an omni-directional manner. On receiving the RTS, the destination node uses selection diversity to determine the direction of the transmitter and points its antenna towards the transmitter. The destination node waits for the transmitter to complete its transmission of the circular RTS and then responds by sending a CTS in the direction of the RTS transmitter. The RTS transmitter hears the CTS in an omni-directional fashion and, using selection diversity, determines the direction from which the CTS packet arrived. It then points its antenna beam in that direction. Once the direction of the transmitter and the receiver are known the nodes preserve these locations in a “Location Table”.
Here, the protocol makes strong assumptions about antenna technology. For example, the protocol relies heavily on selection diversity and negligible switching times. It is not clear how easy it is to implement selection diversity with omni-directional antennas. Additionally, this protocol does not provide for the case when the beam switching time is non negligible. Although slow a switching time is less of a concern in a simple discovery protocol, when the discovery protocol is tied in with the MAC (Media Access Control), as in this scheme, switching times can affect performance. Another weakness of the proposed scheme is the fine time synchronization requirement needed for coordinating the completion of the directional circular RTS with the subsequent CTS response. The destination node determines when the RTS will end by examining the beam number (1 . . . M) which is included as part the RTS packet. Yet another issue is that this protocol does not address the case of asymmetric links. Also, the protocol considers non-overlapping directions for antenna beams. In practice this is almost never achievable. Protocol modifications are necessary when this requirement cannot be met strictly. Another significant disadvantage of this approach is that the protocol does not enable communication between two nodes where the only way they can communicate is through directional transmission and directional reception when both antennas are aimed correctly.
The UDAAN Discovery Protocol (see Ram Ramanathan, Jason Redi, Cesar Santivanez, David Wiggins, Stephen Polit “Ad Hoc Networking with Directional Antennas: A Complete System Solution”, IEEE Journal on Selected Areas in Communications, vol. 23, no. 3, March 2005) does not make a distinction between switched beam and steerable directional antenna, labeling both beam forming (BF) antenna. This protocol considers a mixed node network, where nodes are capable of: a) receiving and transmitting omni-directionally only (N-BF); b) transmitting directionally, but receiving omni-directionally (T-BF); and c) transmitting and receiving directionally (TR-BF).
Each node in the network broadcasts a “hello” message periodically. A node learns about the existence of another nodes by hearing these heartbeat messages. In the case of N-BF, this reduces to a traditional neighbor discovery technique. For T-BF and TR-BF, the protocol describes two discovery methods: informed discovery and blind discovery. The difference between the two has to do with whether or not the node knows about the existence of the destination node. For informed T-BF and TR-BF, the node sends a directional heartbeat, containing its own location, by pointing its antenna in the approximate direction of where it thinks the destination node is. The target node receives the heartbeat in a omni-directional manner, determines the position of the sending node from the message, and then sends its own heartbeat towards the initiating node. For blind T-BF discovery, the node scans through all possible directions, sending a heartbeat in each direction at pre-defined time intervals. When the target receives this message, it starts the informed T-BF process with the initiator of the blind heartbeat. In accomplishing neighbor discovery with blind TR-BF, the protocol requires that the clocks on all nodes be synchronized, possibly with a common clock source such as GPS (Global Positioning System). Periodically all nodes engage in blind TR-BF discovery at the same time. A direction is chosen based on the time and each node alternates randomly between sending a heartbeat in that direction and listening in the opposite direction for such heartbeats. After one complete cycle, all TR-BF neighbors are discovered. Blind TR-BF discovery only works in two dimensions.
As can be seen, due to the high complexity and high cost of the antenna hardware or operation of the above neighbor discovery protocols, each leaves much to be desired. Accordingly, a need exists for a method that efficiently and effectively enables a node to determine the relative location of its neighboring nodes—nodes that are directly reachable via a single hop—in a mesh network. The invention provides such a method. These and other advantages of the invention, as well as additional inventive features, will be apparent from the description of the invention provided herein.